package com.practice.math;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

public class FindVertex {
	ArrayList<Point> findVertices(Rectangle[] r) {
		ArrayList<Point> collector = new ArrayList<Point>();
		HashMap<Rectangle, ArrayList> map = new HashMap<Rectangle, ArrayList>();
		
		Arrays.sort(r, new Comparator<Rectangle>() {
			public int compare(Rectangle a, Rectangle b) {
				return a.getLeft() - b.getLeft();
			}
		});
		
		for (int i=0; i<r.length; i++) {
			ArrayList<Point> v= addVertices(r[i]);
			if (map.size() == 0) {
				map.put(r[i], v);
				continue;
			}
				
			// pop unoverlapped
			ArrayList<Rectangle> keys = new ArrayList<Rectangle>();
			keys.addAll(map.keySet());
			for (Rectangle rec : keys) {
				if (rec.getRight() < r[i].getLeft()) {
					collector.addAll(map.get(rec));
					map.remove(rec);
				}
			}
				
			// calculate overlap
			for (Rectangle rec : map.keySet()) {
				map.get(rec).addAll(overlap(rec, r[i]));
			}
		}
		
		for (Rectangle rec : r) {
			removeInners(rec, collector);
		}
		
		return collector;
	}
	
	private void removeInners(Rectangle rec, ArrayList<Point> list) {
		for (int i=list.size()-1; i>=0; i--) {
			if (rec.contains(list.get(i))) list.remove(i);
		}
	}
	
	private ArrayList<Point> overlap(Rectangle left, Rectangle right) {
		ArrayList<Point> list = new ArrayList<Point>();
		if (left.getRight() <= right.getRight()) {
			if (right.getHeight() > left.getHeight()) {
				list.add( new Point(right.getLeft(), left.getHeight()) );
			}
			else if (right.getHeight() < left.getHeight()) {
				list.add( new Point(left.getRight(), right.getHeight()) );
			}
		}
		else {
			if (right.getHeight() > left.getHeight()) {
				list.add(new Point(right.getLeft(), left.getHeight()));
				list.add(new Point(right.getRight(), left.getHeight()));
			}
		}
		
		return list;
	}
	
	private ArrayList<Point> addVertices(Rectangle r) {
		ArrayList<Point> v = new ArrayList<Point>();
		v.add(new Point(r.getLeft(), 0));
		v.add(new Point(r.getRight(), 0));
		v.add(new Point(r.getLeft(), r.getHeight()));
		v.add(new Point(r.getRight(), r.getHeight()));
		return v;
	}
}
